package graph.directed.topological;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

import graph.directed.loopDetection.CandyDirectedLoopDetection;
import graph.directed.unweighted.CandyDFS;
import graph.unweighted.CandyGraph;
/**
 * 
 * @Title: CandyTopoLogicalSort2.java 
 * @Package graph.directed.topological 
 * @Description: 使用DFS的后序遍历的逆序列完成拓扑排序
 * @author CandyWall   
 * @date 2021年1月22日 下午6:57:05 
 * @version V1.0
 */
public class CandyTopoLogicalSort2 {
    private CandyGraph graph;
    private boolean hasLoop;    // 有向图中是否有环

    public CandyTopoLogicalSort2(CandyGraph graph) {
        if(!graph.isDirected()) {
            throw new IllegalArgumentException("拓扑排序只能用于有向图！");
        }
        this.graph = graph;
    }
    
    /**
     * 获取拓扑排序序列
     * @return
     */
    public ArrayList<Integer> getTopologicalSortOrder() {
        ArrayList<Integer> res = new ArrayList<>();
        CandyDirectedLoopDetection loopDetection = new CandyDirectedLoopDetection(graph);
        if(loopDetection.hasLoop()) {
            hasLoop = true;
            return res;
        }
        
        CandyDFS dfs = new CandyDFS(graph);
        // 获取当前图的深度优先遍历的后序序列
        res = dfs.getPostOrderList();
        // 将序列逆序即为拓扑排序序列
        Collections.reverse(res);
        
        return res; 
    }
    
    public boolean hasLoop() {
        return hasLoop;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/directed/topological/graph1.txt", true);
        CandyTopoLogicalSort2 sort1 = new CandyTopoLogicalSort2(graph1);
        System.out.println(sort1.getTopologicalSortOrder());
        if(sort1.hasLoop()) {
            System.out.println("有向图中检测到环，无法完成拓扑排序！");
        }
        CandyGraph graph2 = new CandyGraph("testData/directed/topological/graph2.txt", true);
        CandyTopoLogicalSort2 sort2 = new CandyTopoLogicalSort2(graph2);
        System.out.println(sort2.getTopologicalSortOrder());
        if(sort2.hasLoop()) {
            System.out.println("有向图中检测到环，无法完成拓扑排序！");
        }
    }
    
}
